<?php

namespace App\Http\Controllers\Queue;
class PriorityTree
{
    private $queue;
    private static $instance = null;
    private function __construct($arrs=null)
    {
        $this->queue = array();
    }

    public function init($arrs){
        foreach ($arrs as $arr){
            $node = new Node($arr['id'],$arr['value']);
            array_push($this->queue,$node);
        }
        $this->heapify();
    }

    public static function getIns(){
        if(!self::$instance instanceof self){
            self::$instance = new self;
        }
        return self::$instance;
    }

    public function current(){
        if($this->isEmpty()){
            return null;
        }

        return $this->queue[0];
    }

    private function __clone()
    {
        // TODO: Implement __clone() method.
        return null;
    }

    public function heapify(){
        $lastNodeIndex = $this->lastChildIndex();
        if($lastNodeIndex  === null)
            return;
        $lastNodeFatherIndex = $this->fatherChildIndex($lastNodeIndex);
        if($lastNodeFatherIndex === null)
            return;
        for($i=$lastNodeFatherIndex;$i>=0;$i--){
            $this->siftDown($i);
        }

    }
    public function getQueue(){
        return $this->queue;
    }
    //使用最小堆
    private function compare($node1,$node2){
        return ($node1->getKey()) > ($node2->getKey());
    }
    public function count(){
        return sizeof($this->queue);
    }
    public function isEmpty(){
        return $this->queue == [];
    }
    private function siftDown($downIndex){
        $downNode = $this->queue[$downIndex];
        while(true){
            $leftNode = $this->leftChildNode($downIndex);
            $rightNode = $this->rightChildNode($downIndex);
            //如果下面没有子节点 下沉已经完成
            if($leftNode === null){
                break;
            }

            if($rightNode === null){
                //换元素
                if($this->compare($downNode, $leftNode)){
                    $this->queue[$downIndex] = $leftNode;
                    $this->queue[$this->leftChildIndex($downIndex)] = $downNode;
                    $downIndex = $this->leftChildIndex($downIndex);
                    continue;
                }else{
                    break;
                }
            }
            //让下沉的和左右小的子节点来比较,和小的节点交换位置
            if($this->compare($this->leftChildNode($downIndex),$this->rightChildNode($downIndex))){
                $compareIndex = $this->rightChildIndex($downIndex);
                $compareNode = $this->rightChildNode($downIndex);
            }else{
                $compareIndex = $this->leftChildIndex($downIndex);
                $compareNode = $this->leftChildNode($downIndex);
            }

            if($this->compare($downNode,$compareNode)){
                $this->queue[$compareIndex] = $downNode;
                $this->queue[$downIndex] = $compareNode;
                $downIndex = $compareIndex;
                continue;
            }else{
                break;
            }
        }
    }
    //shit up操作 value就是里面带上的对象 key就是里面带上的比较值
    public function insert($value,$key){
        $node = new Node($value,$key);
        array_push($this->queue,$node);
        $index = $this->lastChildIndex();
        while (true){
            $fatherIndex = $this->fatherChildIndex($index);
            if($fatherIndex === null)
                return;
            $fatherNode = $this->queue[$fatherIndex];
            //如果父节点比子节点大 那么就交换位置
            if($this->compare($fatherNode , $node)){
                $this->queue[$fatherIndex] = $node;
                $this->queue[$index] = $fatherNode;
                $index = $fatherIndex;
            }else{
                return;
            }
        }
    }
    //弹出操作 把堆顶的元素弹出 把最后一个元素移动到第一个元素位置
    public function extract(){
        if($this->isEmpty())
            return null;
        $popNode = $this->queue[0];
        $downNode =  array_pop($this->queue);
        if($this->isEmpty())
            return $popNode;
        $this->queue[0] = $downNode;
        $downIndex = 0;//开始下沉
        $this->siftDown($downIndex);
        return $popNode;
    }
    //获取左子节点
    private function leftChildNode($index){
        if($index === null)
            return null;
        if($this->leftChildIndex($index) === null)
            return null;
        return $this->queue[$this->leftChildIndex($index)];
    }
    //获取右子节点
    private function rightChildNode($index){
        if($index === null)
            return null;
        if($this->rightChildIndex($index) === null)
            return null;
        return $this->queue[$this->rightChildIndex($index)];
    }

    //获取左子节点的index
    private function leftChildIndex($index){
        if($this->lastChildIndex() === null)
            return null;
        return 2 * $index + 1 > $this->lastChildIndex() ? null : 2*$index + 1;
    }

    //获取右子节点的index
    private function rightChildIndex($index){
        if($this->lastChildIndex() === null)
            return null;
        return 2 * $index + 2 > $this->lastChildIndex() ? null : 2*$index + 2;
    }

    //获取父节点的index
    private function fatherChildIndex($index){
        if($this->lastChildIndex() === null)
            return null;
        if(($index - 1 < 0) or ($index < 0)){
            return null;
        }
        return (int) floor(($index-1)/2);
    }

    //获取最后一个节点的index
    private function lastChildIndex(){
        return $this->count() == 0 ? null:$this->count()-1;
    }

}